<html>

<head>
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8"> 
  <link rel="stylesheet" title="Default" href="http://acm.math.spbu.ru/~sk1/colorer/my.css">

  <script src="http://acm.math.spbu.ru/~sk1/colorer/highlight.js"></script>
  <script src="http://acm.math.spbu.ru/~sk1/colorer/cpp.js"></script>
  <script>hljs.initHighlightingOnLoad();</script>
</head>

<body>

<pre><code>
const int maxn = 1 &lt;&lt; 15;

ll init = 0, sum;
int n, m, val[maxn * 2], is[maxn * 2];
ll f[maxn * 2];

ll Get( int v, int vl, int vr, int l, int r )
{
  if (r &lt; vl || vr &lt; l)
    return 0;
  if (is[v])
    return (ll)val[v] * (min(vr, r) - max(vl, l) + 1);
  if (l &lt;= vl && vr &lt;= r)
    return f[v];
  int vm = (vl + vr) / 2;
  return Get(2 * v, vl, vm, l, r) + Get(2 * v + 1, vm + 1, vr, l, r);
}

void Set( int v, int vl, int vr, int l, int r, int newVal )
{
  if (r &lt; vl || vr &lt; l)
    return;
  if (l &lt;= vl && vr &lt;= r)
  {
    is[v] = 1, val[v] = newVal, f[v] = (ll)newVal * (vr - vl + 1);
    return;
  }
  if (is[v])
  {
    is[v] = 0;
    is[2 * v] = is[2 * v + 1] = 1;
    val[2 * v] = val[2 * v + 1] = val[v];
    f[2 * v] = f[2 * v + 1] = f[v] / 2;
  }
  int vm = (vl + vr) / 2;
  Set(2 * v, vl, vm, l, r, newVal);
  Set(2 * v + 1, vm + 1, vr, l, r, newVal);
  f[v] = f[2 * v] + f[2 * v + 1];
}

forn(i, n)
{
  int x;
  scanf("%d", &x), init += x;
  f[maxn + i] = x;
}
sum = init;
fornd(i, maxn)
  f[i] = f[2 * i] + f[2 * i + 1];

</code></pre>

</body>
</html>

<font style="visibility:hidden">
